package com.example.skiplist17.lx;

import org.junit.jupiter.api.Test;

import java.util.Random;

/**
 * @description
 * @auther lijiewei
 * @date 2021/7/21 16:57
 */
public class SkipList2 {

    @Test
    public void SkipListTest() throws Exception{
        SkipList2 list = new SkipList2();
        list.insert(1, 3);
        list.insert(2, 3);
        list.insert(3, 2);
        list.insert(4, 4);
        list.insert(5, 10);
        list.insert(6, 4);
        list.insert(8, 5);
        list.insert(7, 4);
        list.printAll_beautiful();
        list.printAll();
    }

    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;
    /**
     * 带头链表
     */
    private Node head = new Node(MAX_LEVEL);
    private Random r = new Random();

    public Node find(int value) {
        Node p = head;
        // 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一节点
                p = p.forwards[i];
            }
        }

        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        } else {
            return null;
        }
    }

    /**
     * 优化后的插入方式3
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/7/26 14:31
     */
    public void insert3(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        //每次只增加一层，如果条件满足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node[] update = new Node[level];
        for (int i = 0; i< level; ++i) {
            update[i] = head;
        }
        Node p = head;
        //从最大层开始查找，找到前一节点，通过--i,移动到下层再开始查找
        for (int i = levelCount-1; i >=0 ; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一节点
                p = p.forwards[i];
            }
            // levelCount 会 > level，所以加上判断
            if (level > i) {
                update[i] = p;
            }
        }
        for (int i = 0; i < level; ++i) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }
    }

    /**
     * 优化后的插入方式2
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/7/26 13:48
     */
    public void insert2(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        //每次只增加一层，如果条件满足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node p = head;
        //从最大层开始查找，找到前一节点，通过--i,移动到下层再开始查找
        for (int i = levelCount-1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                //找到前一节点
                p = p.forwards[i];
            }
            //levelCount 会>level, 所以加上判断
            if (level > i) {
                if (p.forwards[i] == null) {
                    p.forwards[i] = newNode;
                } else {
                    Node next = p.forwards[i];
                    p.forwards[i] = newNode;
                    newNode.forwards[i] = next;
                }
            }
        }
    }

    /**
     * 未优化前的inset方法
     * @param value 插入值
     * @param level 层级，0为底层
     * @return
     * @author lijiewei
     * @date   2021/7/26 10:50
     */
    public void insert(int value, int level) {
        //随机一个层数
        if (level == 0) {
            level = randomLevel();
        }

        //创建新节点
        Node newNode = new Node(level);
        newNode.data = value;
        //表示从最大层到低层，都要有节点数据
        newNode.maxLevel = level;
        //记录要更新的层数，表示新节点要更新到哪层
        Node[] update = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        //层是从下到上的，这里最下层编号是0 ，最上层编号是15
        //这里没有从已有数据最大层（编号最大）开始找，（而是从随机层数开始找）
        //会导致如果数据量很大，但是随机level为1,变成了遍历，时间复杂度为O(n)
        Node p = head;
        for (int i = level-1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            //这里update[i]表示当前层节点的前一节点，因为要找到迁移节点，才好插入数据
            update[i] = p;
        }

        //将每一层节点和后面节点关联
        for (int i = 0; i < level; ++i) {
            //记录当前层节点后面节点指针
            newNode.forwards[i] = update[i].forwards[i];
            //前一节点的指针，指向当前节点
            update[i].forwards[i] = newNode;
        }

        //更新层高
        if (levelCount < level) {
            levelCount = level;
        }
    }

    public void delete(int value) {
        Node[] update = new Node[levelCount];
        Node p = head;
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            update[i] = p;
        }

        if (p.forwards[0] != null && p.forwards[0].data == value) {
            for (int i = levelCount - 1; i >= 0; --i) {
                if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
                    update[i].forwards[i] = update[i].forwards[i].forwards[i];
                }
            }
        }
    }

    /**
     * 打印每个节点数据和最大层数
     */
    public void printAll() {
        Node p = head;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    /**
     * 打印所有数据
     */
    public void printAll_beautiful() {
        Node p = head;
        Node[] c = p.forwards;
        Node[] d = c;
        int maxLevel = c.length;
        for (int i = maxLevel - 1; i >= 0; i--) {
            do {
                System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
            } while (d[i] != null && (d = d[i].forwards)[i] != null);
            System.out.println();
            d = c;
        }
    }


    /**
     * 随机层数，如果是奇数层就+1，防止伪随机
     * @param null
     * @return
     * @author lijiewei
     * @date   2021/7/26 10:54
     */
    private int randomLevel() {
        int level = 1;
        for (int i=1; i<MAX_LEVEL; ++i) {
            if (r.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    /**
     * 跳表的节点，每个节点记录了当前节点数据和所在层数数据
     */
    public class Node {
        private int data = -1;
        /**
         * 表示当前节点位置的下一个节点所有层的数据，从上层切换到下层，就是数组下标-1，
         * forwards[3]表示当前节点在第三层的下一个节点。
         */
        private Node forwards[];

        /**
         * 这个值其实可以不用，看优化insert()
         */
        private int maxLevel = 0;

        public Node(int level) {
            forwards = new Node[level];
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");
            return builder.toString();
        }
    }

}
